#include <stdio.h>

int merge(int a[], int mid, int n, int tmpa[]) {
    int i=0, j=mid, k=0;
    int rp = 0;
    while(i<mid && j<n) {
        if(a[i]<=a[j]) {
            tmpa[k++] = a[i++];
        }else {
            tmpa[k++] = a[j++];
            rp += mid-i;
        }
    }
    while(i<mid) {
        tmpa[k++] = a[i++];
    }
    while(j<n) {
        rp += mid-i;
    }
    for(i=0; i<k; i++)
        a[i] = tmpa[i];
    return rp;
}


int merge_sort_core(int a[], int n, int tmpa[]) {
    if(n<2) return 0;
    int mid = n/2;
    int lrp = merge_sort_core(a, mid, tmpa);
    int rrp = merge_sort_core(a+mid, n-mid, tmpa);
    return lrp+rrp+merge(a, mid, n, tmpa);
}
int merge_sort(int a[], int n) {
    int *tmpa = new int[n];
    int rpc = merge_sort_core(a, n, tmpa);
    delete [] tmpa;
    return rpc;
}

int main(void) {
    int a[] = {5, 4, 3, 2, 1};
    printf("rp cnt: %d\n", merge_sort(a, 5));
}
